package lib

//link to 875 410 1011
func init() {
	Probs = append(Probs, Problem{
		Num:         1231,
		Discription: "将巧克力切成k块，求其中最不甜的一块的甜度的最大值",
		Level:       3,
		Labels: map[string]int{
			"二分查找": 1,
			"单调函数二分":   1,
		},
	})
}

func MaximizeSweetness(sweetness []int, k int) int {
	//在保证每块甜度>=minSweetness的情况下，是否能分成k+1块
	satisfyK := func(minSweetness int) bool {
		curSum := 0
		count := 0
		for _, val := range sweetness {
			curSum += val
			if curSum >= minSweetness {
				count++
				curSum = 0
			}
		}

		//如果最终能分成k+1块以上，合并成k+1块时，肯定也是满足甜度条件的
		return count >= k+1
	}

	left := sweetness[0]
	sum := sweetness[0]
	for i := 1; i < len(sweetness); i++ {
		left = min(left, sweetness[i])
		sum += sweetness[i]
	}
	right := sum

	for left < right {
		mid := left + (right-left+1)/2
		if satisfyK(mid) {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}